package stack_queue;

import java.util.Deque;
import java.util.LinkedList;

public class ReverseLinkedList {
    static class Node{
        int val;
        Node next;

        Node(int val){
            this.val = val;
            this.next = null;
        }
    }

    //输入：1 -> 2 -> 3 -> 4
    //输出：4、3、2、1
    private static void reverseLinkedList1(Node head){
        //使用栈
        Deque<Integer> stack = new LinkedList<>();
        //遍历链表，让链表的元素逐个入栈
        Node cur = head;
        while(cur != null){
            int e = cur.val;
            stack.push(e);
            cur = cur.next;
        }
        //栈中元素逐个出栈
        while(!stack.isEmpty()){
            int e = stack.pop();    //栈中元素是包装类Integer,自动拆箱
            System.out.println(e);
        }
    }

    //输入：1 -> 2 -> 3 -> 4
    //输出：4、3、2、1
    private static void reverseLinkedList2(Node head){
        //利用递归(实际上利用调用栈(调用栈也是栈)完成逆置)
        if(head == null){
            return;
        }
        reverseLinkedList2(head.next);
        System.out.println(head.val);
    }

    public static void main(String[] args) {
        Node n1 = new Node(100);
        Node n2 = new Node(200);
        Node n3 = new Node(300);
        Node n4 = new Node(400);
        Node n5 = new Node(500);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;

        reverseLinkedList1(n1);
        System.out.println("-----------");
        reverseLinkedList2(n1);

    }

}
